/*
题目: 第 N 个神奇数字
一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
https://leetcode.cn/problems/nth-magical-number/description/
 */
public class NthMagicalNumber {
    private final long MOD = (long) 1e9 + 7;
    public int nthMagicalNumber(int n, int a, int b) {
        // 题目描述: 找到第 n 个神奇数字 -> 「 <= x 的神奇数字的个数为 n」

        // 找到 f(x) = n ，也就是找到一个 x ，让 <= x 的个数 为 n
        // [0, x] 区间能够被 num 整除的个数有 x / num 个
        // f(x) = x / a + x / b + x / lcm(a, b)
        long lcm = getLcm(a, b);
        long left = Math.min(a, b), right = (long)n * Math.min(a, b); // 此处的 n 一定要加上 long 进行强转
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = mid / a + mid / b - mid / lcm;
            if (count >= n) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (int) ((right + 1) % MOD);
    }

    // 最大公约数
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    // 最小公倍数
    private int getLcm(int a, int b) {
        if (a < b)  return getLcm(b, a);
        return a * b / gcd(a, b);
    }
}
